#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-16 11:04 上午
# @Author  : yangdy
# @File    : 2020-07-16.785. 判断二分图
# @Software: PyCharmCE
from typing import List


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        ans = True
        n = len(graph)
        colors = [-1 for i in range(n)]

        def dfs(x, c):
            for y in graph[x]:
                if colors[y] == -1:
                    colors[y] = 1-c
                    if not dfs(y, 1-c):
                        return False
                elif colors[y] == c:
                    return False
            return True

        for i in range(n):
            if colors[i] == -1:
                colors[i] = 0
                if not dfs(i, 0):
                    ans = False
                    break

        return ans


solve = Solution()

questions = [
    ([[1, 3], [0, 2], [1, 3], [0, 2]], ),
    ([[1, 2, 3],  [0, 2],  [0, 1, 3],  [0, 2]], ),
    ([[], [2, 4, 6], [1, 4, 8, 9], [7, 8], [1, 2, 8, 9], [6, 9], [1, 5, 7, 8, 9], [3, 6, 9], [2, 3, 4, 6, 9], [2, 4, 5, 6, 7, 8]], ),
    ([[1, 3], [0, 2], [1, 3], [0, 2]], ),
    ([[2, 3, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 4, 5, 6, 7, 8, 9], [1, 2, 3, 6, 9], [0, 1, 2, 3, 7, 8, 9], [0, 1, 2, 3, 4, 7, 8, 9], [0, 1, 2, 3, 5, 6, 8, 9], [0, 1, 2, 3, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7]], ),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.isBipartite(graph=q[0]))
